package com.algorithm2;

import java.util.Arrays;

public class MergeSort2 {
    public static void main(String[] args){
        int[] array = new int[]{0,8, 9, 3,10, 2, 4, 5, 6, 7, 1};
        int[] rest = mergeSort(array);
        System.out.println("排序完数据:"+ Arrays.toString(rest));
    }
    public static int[] mergeSort(int[] array){
        int[] arr = array;//Arrays.copyOf(array, array.length);
        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);
        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);
        return merge(mergeSort(left), mergeSort(right));

    }
    protected static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        int leftSize = left.length;
        int rightSize = right.length;
        int leftCount = 0;
        int rightCount = 0;
        while((0 <= leftCount && leftCount <leftSize) && (0 <= rightCount && rightCount <rightSize)){
                if(left[leftCount]<right[rightCount]){
                    result[i++] = left[leftCount++];
                }else{
                    result[i++] = right[rightCount++];
                }
        }

        if(leftCount==leftSize){
            while(rightCount!=rightSize){
                result[i++] = right[rightCount++];
            }
        }
        if(rightCount==rightSize){
            while(leftCount!=leftSize){
                result[i++] = left[leftCount++];
            }
        }
        System.out.println("left:"+Arrays.toString(left)+"-->right:"+Arrays.toString(right)+">>result:"+Arrays.toString(result));
        /*while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }*/

        return result;
    }


}
